//
// Created by Administrator on 2021/5/5.
//

/*
给你一个整数数组nums，你可以对它进行一些操作。

每次操作中，选择任意一个nums[i]，删除它并获得nums[i]的点数。之后，
 你必须删除每个等于nums[i] - 1或nums[i] + 1的元素。

开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。


示例 1：
输入：nums = [3,4,2]
输出：6
解释：
删除 4 获得 4 个点数，因此 3 也被删除。
之后，删除 2 获得 2 个点数。总共获得 6 个点数。

示例2：
输入：nums = [2,2,3,3,3,4]
输出：9
解释：
删除 3 获得 3 个点数，接着要删除两个 2 和 4 。
之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
总共获得 9 个点数。

提示：

1 <= nums.length <= 2 * 104
1 <= nums[i] <= 104

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/delete-and-earn
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/
#include <vector>
#include <iostream>
#include <map>
#include <algorithm>

using namespace std;

class Solution {
public:
    int deleteAndEarn(vector<int> &nums) {
        if (nums.empty()) return 0;
        // 统计每个数字的个数
        map<int, int> counter;  // 有序
        for (const auto &x:nums) ++counter[x];
        // 构造dp数组
        int MAX_VAL = (--counter.end())->first; // 最大的元素
        vector<pair<int, int>> dp(MAX_VAL + 1, pair<int, int>{0, 0});
        for (int i = 1; i <= MAX_VAL; ++i) {
            if (counter[i] == 0) { // 未出现这个数
                dp[i].first = dp[i].second = max(dp[i - 1].first, dp[i - 1].second);
            } else {
                dp[i].first = dp[i - 1].second + counter[i] * i; // 选这个数 只能是上个数不选
                dp[i].second = max(dp[i - 1].first, dp[i - 1].second);// 不选这个数，可能是上个数选或者不选
            }
        }
        return max(dp.back().first, dp.back().second);
    }
};

class Solution2 { // 题解 1
private:
    int rob(vector<int> &nums) { // 同198 打家劫舍
        auto size = nums.size();
        int first = nums[0], second = max(nums[0], nums[1]);
        for (int i = 2; i < size; i++) {
            int temp = second;
            second = max(first + nums[i], second);
            first = temp;
        }
        return second;
    }

public:
    int deleteAndEarn(vector<int> &nums) {
        int maxVal = 0;
        for (int val : nums) {
            maxVal = max(maxVal, val); // nums的最大值
        }
        vector<int> sum(maxVal + 1);
        for (int val : nums) {
            sum[val] += val;  // 统计各个元素之和
        }
        return rob(sum); // 调用打家劫舍的思路
    }
};

class Solution3 { // 题解 排序+dp
private:
    int rob(vector<int> &nums) {  // 打家劫舍
        auto size = nums.size();
        if (size == 1) {
            return nums[0];
        }
        int first = nums[0], second = max(nums[0], nums[1]);
        for (int i = 2; i < size; i++) {
            int temp = second;
            second = max(first + nums[i], second);
            first = temp;
        }
        return second;
    }

public:
    int deleteAndEarn(vector<int> &nums) {
        auto n = nums.size();
        int ans = 0;
        sort(nums.begin(), nums.end()); // 排序
        vector<int> sum = {nums[0]};
        for (int i = 1; i < n; ++i) {
            int val = nums[i];
            if (val == nums[i - 1]) {  // 相同元素
                sum.back() += val;
            } else if (val == nums[i - 1] + 1) {  // 相邻元素
                sum.push_back(val);
            } else {
                ans += rob(sum); // 不相邻的 执行打家劫舍
                sum = {val};
            }
        }
        ans += rob(sum);
        return ans;
    }
};


int main() {
    vector<int> v1{2, 2, 3, 3, 3, 4};
    vector<int> v2{3, 4, 2};
    Solution2 sol;
    cout << sol.deleteAndEarn(v1) << endl;
    cout << sol.deleteAndEarn(v2) << endl;
    return 0;
}